A “finite state machine” is often used for finding patterns in an input string. For example, such machines are used for parsing language to detect words. A finite state machine is defined to be a machine that has a plurality of states and a rule that provides the next state of the machine given the current state and the next character in the input string being processed by the finite state machine. The set of states also includes an initial state in which the machine resides prior to the receipt of the first character in the input stream. The finite state machine generates outputs when some of the states are entered. These outputs form the outputs of the finite state machine.
Consider a finite state machine that is part of a spelling checker for a word processing program. The input stream is the document viewed as a continuous string of characters that include the alphabet and various punctuation marks. As the input string is processed one character at a time, the finite state machine moves from state to state according to the rules specified by the finite state machine. Some of the states correspond to a word being detected. When these states are entered, the finite state machine provides a corresponding output to the part of the checker that looks up the word in a dictionary.
Finite state machines are potentially useful for processing signals in instruments such as oscilloscopes to detect specific patterns in the signals. Consider the case in which the input signal that varies from 0 to 1 volt is digitized into one of three “characters”. The first character corresponds to a low state and represents signals from 0 to 0.1 volts. The second character is an intermediate state that represents signals that are greater than 0.1 volts to 0.9 volts. The third character is a high state that represents signals that are greater than 0.9 volts to 1 volt. The number of states will depend on the specific characteristics that are to be recognized. The finite state machine typically implements its processing algorithm by storing a table having one row per state and one column for each possible input table. The table entries are next state of the finite state machine. That is, the entry in row, r, at column c, is the state to which the finite state machine is to assume if character “c” is received while the finite state machine is in state “r”.
Parsing programs for text operate on input files that have a relatively small number of characters in the input string, typically less than 100,000 characters. A modern desktop computer can process such strings in real time as the user types or parse a stored file in a relatively short period of time. In contrast, a parsing program that operates on a digitized electrical signal must deal with much larger input streams. For example, consider a high frequency signal that is sampled every ns for 100 seconds. The resultant input sequence contains 1011 characters. If it takes only 100 ns per symbol to process the stream, the processing time is still 104 seconds, i.e., approximately 3 hours. Such processing times are unacceptable in many applications.
In principle, the processing time should be capable of being reduced by employing multiple processors to process the input stream. Multi-processor computers and graphic cards having multiple processors that operate in parallel are now commonplace. High-end graphic cards include hundreds of processors that can be used for general purpose computing as well as specialized graphic computations. However, satisfactory algorithms for applying multiple processors to the problem in a manner that reduces the overall processing time to less than that encountered with a single processor are not available for many applications.